package com.chilly.stack;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * 20 有效的括号
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
 * 有效字符串需满足：
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 * 注意空字符串可被认为是有效字符串。
 * <p>
 * 算法流程
 * 如果 c 是左括号，则入栈 push；
 * 否则通过哈希表判断括号对应关系，若 stack 栈顶出栈括号 stack.pop() 与当前遍历括号 c 不对应，则提前返回 false
 * <p>
 * Created by Chilly Cui on 2020/11/24.
 */
public class ValidParentheses {
    public static void main(String[] args) {
        //测试用例
//        System.out.println(new Solution().isValid(""));//true
//        System.out.println(new Solution().isValid("()"));//true
//        System.out.println(new Solution().isValid("()[]{}"));//true
//        System.out.println(new Solution().isValid("{[]}"));//true
//        System.out.println(new Solution().isValid("(]"));//false
//        System.out.println(new Solution().isValid("([)]"));//false
//        System.out.println(new Solution().isValid(")"));//false
        System.out.println(new Solution().isValid("("));//false
    }
}

class Solution {
    //建立哈希表 dic 构建左右括号对应关系：key 左括号，value 右括号
    private final static Map<Character, Character> map = new HashMap<Character, Character>() {
        {
            put('{', '}');
            put('[', ']');
            put('(', ')');
            put('?', '?');
        }
    };

    /**
     * @param s 字符串只包括 '('，')'，'{'，'}'，'['，']'
     * @return
     */
    public boolean isValid(String s) {
        if (s.isEmpty()) return true;
        if (s.length() % 2 == 1) {
            return false;
        }
        if (s.length() > 0 && !map.containsKey(s.charAt(0))) return false;
        LinkedList<Character> stack = new LinkedList<Character>() {{
            add('?'); //此时当 stack 为空且 c 为右括号时，可以正常提前返回 false；
        }};
        for (Character c : s.toCharArray()) {
            if (map.containsKey(c)) stack.addLast(c);
            else if (map.get(stack.removeLast()) != c) return false;
        }
        return stack.size() == 1;
    }

    /*public boolean isValid(String s) {
        if (s.isEmpty()) return true;

        Stack<Character> stack = new Stack<Character>();
        for (char c : s.toCharArray()) {
            if (c == '(')
                stack.push(')');
            else if (c == '{')
                stack.push('}');
            else if (c == '[')
                stack.push(']');
            else if (c != stack.pop()) //如果栈顶弹出的括号和此时的c不匹配直接返回false
                return false;
        }
        if (stack.isEmpty())
            return true;
        return false;
    }*/
}